package leetcode_1_20;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Nconvert_6 {
    /**
     * 6，N 字形变换
     * 首先尝试二维数组，算法比较繁琐
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {
        int group = (numRows - 1) * 2 , p;  //一组
        if(numRows==1)
            return s;
        p =  (s.length()%group) < numRows  ?  1  : (s.length() % group-numRows+1);   //最后不满一组的列数,0组也算一组
        if(s.length()%group ==0 )
            p--;
        int column= s.length()/group*(group-numRows+1)+  p ; //列数

        char[][]arr=new char[numRows][column];
        List<Character> list=s.chars()
                .mapToObj(c -> (char) c)
                .collect(Collectors.toList());
        int index=0;
        String r = "";
        int flag=0;      //判断是否跳到下一列的标志
        for (int i=0; i< column;i++) {
            for (int t=0; t<numRows;t++) {
                int n=(index+1) % group;
                if(index == s.length())
                    break;
                if( ((n <= numRows) && n != 0 ) || numRows==2) {
                    //说明该列按顺序全部需要赋值,当numRows=2 该列也需要全部赋值
                    arr[t][i] = list.get(index++);
                    flag=1;
                }
            }
            if(flag==1 || index == s.length() || numRows==2){
                flag=0;
                continue;
            }
            int n=(index+1) % group;
            if( n > numRows || n == 0){
                if ( n == 0)    //如果是上一组的最后一个直接确定行数
                    arr[1][i]=list.get(index++);
                else
                    arr[ 2*numRows-1 -n] [i]=list.get(index++);
            }
            flag=0;
        }
        for (int i=0; i< numRows;i++) {
            for (int t=0; t < column;t++) {
                if(arr[i][t] != '\u0000')
                    r+=arr[i][t];
            }
        }
        return r;
    }


    /**
     * 6.1，N 字形变换
     * 每位数字有特定顺序
     * 实际就是给s的每一位标记就好了：假设numRows为4，那就是那s每一位的行数就是：1234321234321
     * 之间的距离也会根据行数的不同规律变化
     * @param s
     * @param numRows
     * @return
     */
    public static String convert1(String s, int numRows) {
        String r="";
        if(numRows==1)
            return s;
        int group = (numRows - 1) * 2,p;  //一组
        p =  (s.length()%group) < numRows  ?  1  : (s.length() % group-numRows+1);   //最后不满一组的列数,0组也算一组
        int column= s.length()/group*(group-numRows+1)+  p ; //列数
        char[] chars=s.toCharArray();
        int index=0;
        int num_count[] =new int[numRows];   //每一行的间隔数字个数
        for (int i=0;i<numRows;i++){
            if(p>1)                             //不满一组的列数大于1，则直接看前面间隔数字个数
                num_count[i]=( column - 1 ) / (numRows - 1) + 1;
            else{
                int a = ((s.length() % group )- ( i + 1 ) ) >= 0  ? 1: 0;
                num_count[i]= ( column - 1 ) / (numRows - 1) + a;
            }
        }
        for (int i=0;i<numRows;i++){
            if( i == 0) {             //第一行
                int count = 0;
                while ( count < num_count[i]) {
                    r += chars[index];
                    index += group;
                    count++;
                }
            }
            else if(i== numRows-1){      //最后一行
                index=i;
                while (index < s.length()) {
                    r += chars[index];
                    index += group;
                }
            }
            else {
                index = i;
                int left=(numRows-i -1)*2;      //中间数字距离左右数字的下标差
                int right=group-left;
                int count = 0;
                while (count < num_count[i]) {  //计算出作为间隔数字数字的个数
                    r += chars[index];
                    index+=left;
                    int x =   ((index+1)%group) < numRows  ?  1  : ((index+1) % group-numRows+1);                   //最后不满一组的列数
                    int c =  (index+1)/group*(group-numRows+1)+  x ;  //列数
                    if(  c <= column){            //如果不超过列数赋值
                        r += chars[index];
                        index+=right;
                    }
                    count++;
                }
            }
        }
        return r;
    }

    /**
     * 6.2，N 字形变换
     * 对 6.1 逻辑的优化
     * @return
     */
    public static String convert2(String s, int numRows) {
        char[] chars=s.toCharArray();
        int n = s.length();
        int r = numRows;
        if(r < 2 || n <= r)
        {
            return s;
        }
        String end = "";
        int num = 2*r-2;//每周期的元素个数
        int cycle = n % num == 0 ? n / num : ( n / num ) + 1;//周期数

        //第一行
        for(int i = 0; i < cycle; i++)
        {
            if(i*num<n) end+=chars[i*num];
        }

        //第2~r-1行
        for(int j = 1; j < r - 1; j++)
        {
            for(int k = 0; k < cycle; k++)
            {
                if((k*num)+j < n)  end += chars[k*num+j];

                if(((k+1)*num)-j <n)  end +=chars[(k+1)*num-j];
            }
        }
        //第r行
        for(int i = 0; i < cycle; i++)
        {
            if(i*num+r-1 < n) end += chars[i*num+r-1];
        }

        return end;
    }

    /**
     * 6.3，N 字形变换
     * temp 数组 中存放 numRows个字符串
     * 将N字形，拆分为一竖加一斜的重复结构，且一竖和一斜数量相同都是 numRows-1
     * 对于输入的字符串s，其下标 i / (numRows-1) 如果为偶数或零，则代表该下标代表的字符在Z字型中属于竖列。
     * 如果 i / (numRows-1) 如果为奇数，则代表该下标代表的字符在N字型中属于斜列（Z字型的中间倾斜部分）。
     * 如果当前字符属于竖列，则按照正序从第1行整序向下依次保存，
     * 如果属于斜列，则逆行序保存。 从n行逆序向上保存到第2行，一行一个
     * 最后将 temp 数组依次按序输出就是最终答案。
     * @return
     */
    public static String convert3(String s, int numRows) {
        String r="";
        String [] temp=new String[numRows];
        Arrays.fill(temp, "");
        char[] chars=s.toCharArray();
        if(numRows==1)
            return s;
        //ans代表第n段，remain代表每段的第m个元素 m从0开始
        for(int i = 0; i < s.length(); i++){
            int ans = i / (numRows-1);
            int remain = i % (numRows-1);
            if(ans % 2 == 0){                           //结果为偶数或0
                temp[remain]+=chars[i];              //按照正序从第1行整序向下依次保存，
            }
            if(ans % 2 != 0){                           //结果为奇数
                temp[numRows-remain-1]+=chars[i];    //关键算法，如果属于斜列，则逆行序保存。 从n行逆序向上保存到第2行，一行一个
                // numRows-remain-1 也可以写为 numRows-1 - remain 第1个元素即为第n行，第二个元素即为第n-1 行
            }
        }
        for(int i = 0; i < temp.length; i++){
            r += temp[i];
        }
        return r;
    }
}
